#!/usr/bin/python
"""
Virtual Machine for Kitsch

Interprets/executes intermediate assembly-like language

See http://code.google.com/p/kitsch/ for more details
"""

import sys

# verbose output (print memory+stack after each instruction)
verbose = False
#verbose = True

# A list for the VM's stack
stack = []
# A dictionary used to keep track of the program memory, the key is the address
memory = {}
# A stack pointer, our machine's only register
sp = 0

# Add the top two values on the stack
def add(args=[]):
    stack.append(stack.pop() + stack.pop())
    
# Subtract top two values on the stack
def sub(args=[]):
    stack.append(stack.pop() - stack.pop())
    
# Multiply top two values on the stack
def mul(args=[]):
    stack.append(stack.pop() * stack.pop())
    
# Divide top two values on the stack
def div(args=[]):
    try:
        stack.append(stack.pop() / stack.pop())
    except ZeroDivisionError,e:
        print "Fatal: divide by 0."
        sys.exit(1)
        
# Find modulus of top two values on the stack
def mod(args=[]):
    try:
        stack.append(stack.pop() % stack.pop())
    except ZeroDivisionError,e:
        print "Fatal: divide by 0."
        sys.exit(1)
        
# Bitwise AND
def andi(args=[]):
    stack.append(stack.pop() & stack.pop())
    
# Bitwise OR
def ori(args=[]):
    stack.append(stack.pop() | stack.pop())

# Bitwise XOR
def xori(args=[]):
    stack.append(stack.pop() ^ stack.pop())

# Bitwise NOT
def noti(args=[]):
    stack.append(~stack.pop())

"""
Interprets the string argument for load/store/branches
If it is an immediate value, prefaced by a '#', then it returns
the value.

Stack relative addressing: not prefaced with anything
Absolute addressing: prefaced with '&'
Indirect addressing: prefaced with '@'

If it is not an immediate value - it is an address, and it fetches the
value at that address from the memory dictionary
"""
def getValue(arg):
    # Check for immediate value vs. memory address
    if arg.startswith("#"):
        try:
            value = int(arg[1:])
        except ValueError,e:
            raise Exception("Invalid immediate value.")
    elif arg.startswith('"') and arg.endswith('"'):
        value = str(arg[1:-1])
    elif arg.startswith("@"):
        try:
            pointer_address = int(arg[1:])+sp
            address = int(memory[pointer_address])
            value = memory[address]
        except KeyError,e:
            raise Exception("Invalid address. No value initialized at this address")
    elif arg.startswith("&"):
        try:
            address = int(arg[1:])
            value = memory[address]
        except KeyError,e:
            raise Exception("Invalid address. No value initialized at this address")
    else:
        try:
            address = int(arg)+sp
            value = memory[address]
        except ValueError,e:
            raise Exception("Invalid address value. Must be a positive integer")
        except KeyError,e:
            raise Exception("Invalid address. No value initialized at this address")  
    return value            
   
# Load a value from the memory and put it on the stack 
def load(args):
    value = getValue(args[0])
    stack.append(value)
        
# Pop top value from stack and store it at specified memory location
def store(args):
    try:
        if args[0].startswith("@"):
            pointer_address = int(args[0][1:])+sp
            address = memory[pointer_address]
            if verbose:
                print "Indirect addressing:","Pointer address=",pointer_address,", address=",address
        elif args[0].startswith("&"):
            address = int(args[0][1:])    
        else:
            address = int(args[0])+sp
        memory[address] = stack.pop()
    except IndexError,e:
        raise Exception("Runtime Error: Nothing on the stack to store!")
    except ValueError,e:
        raise Exception("Invalid address, must be an integer")
    except KeyError,e:
        raise Exception("Runtime Error: Invalid pointer address.")
        
# Pushes the current memory stack pointer onto the computational stack
def loadsp(args):
    try:
        stack.append(int(sp))
    except ValueError,e:
        raise Exception("Invalid address, must be an integer")
        
# Pops the value from the top of the computational stack and sets the memory stack pointer to it
def storesp(args):
    global sp
    sp = stack.pop()
        
# Parses a branch offset argument, makes sure it is valid.
def validateOffset(offset):
    try:
        if offset.startswith("#"):
            offset = int(offset[1:])
            if pc+offset < 0:
                raise Exception("Invalid offset value. Cannot access negative memory address")
            else:
                return offset
        else:
            raise Exception("Invalid offset value. Must be an immediate value (prefaced with '#')")
    except ValueError,e:
        raise Exception("Invalid offset value. Must be a positive integer")
    
# Branch if equal
def beq(args):
    global pc
    offset = validateOffset(args[0])
    if stack.pop() == stack.pop():
        pc += offset-1
    
# Brach if not equal
def bne(args):
    global pc
    offset = validateOffset(args[0])
    if stack.pop() != stack.pop():
        pc += offset-1

# Branch if less than
def blt(args):
    global pc
    offset = validateOffset(args[0])
    if stack.pop() < stack.pop():
        pc += offset-1
            
# Branch if less than or equal to
def ble(args):
    global pc
    offset = validateOffset(args[0])
    if stack.pop() <= stack.pop():
        pc += offset-1
            
# Branch if greater than
def bgt(args):
    global pc
    offset = validateOffset(args[0])
    if stack.pop() > stack.pop():
        pc += offset-1
            
# Branch if greather than or equal to
def bge(args):
    global pc
    offset = validateOffset(args[0])
    if stack.pop() >= stack.pop():
        pc += offset-1

# Unconditional branch
def bra(args):
    global pc
    pc += validateOffset(args[0])-1
    
# Unconditional branch to absolute address (not relative)
def jmp(args):
    global pc
    pc = getValue(args[0])

# Read a value from standard-input (must be follow by newline)
def readint(args=[]):
    value = raw_input()
    try:
        value = int(value)
        stack.append(value)
    except ValueError,e:
        raise Exception("Invalid input '%s'. Must be an integer." % value)
        
def readstr(args=[]):
    value = eval(repr(raw_input()).replace("\\\\","\\"))
    stack.append(value)
    
def readbool(args=[]):
    value = raw_input().lower()
    if value == "true":
        stack.append(1)
    elif value == "false":
        stack.append(0)
    else:
        raise Exception("Invalid input '%s'. Must be 'true' or 'false'." % value)

# Print value on top of stack
def pnt(args):
    #load(args)
    print stack.pop()
    
# No-operation
def noop(args=[]):
    pass
    
# Substring
def substr(args=[]):
    string = stack.pop()
    startindex = stack.pop()
    endindex = stack.pop()
    
    while startindex < 0:
        startindex += len(string)
        
    while endindex < 0:
        endindex += len(string)
        
    if startindex == 0 and endindex == 0:
        # Special case for the whole string, if the user does mystring[:] in Kitsch code
        stack.append(string[:])
    elif endindex == 0:
        # if endindex is specified as 0, it means goto the end of the string
        stack.append(string[startindex:])
    else:
        stack.append(string[startindex:endindex])

# Concatenates two strings
def stradd(args=[]):
    stack.append(stack.pop()+stack.pop())
    
# Conversion to integer
def toint(args=[]):
    stack.append(int(stack.pop()))
    
# Conversion to string
def tostr(args=[]):
    stack.append(str(stack.pop()))
   
# Conversion to boolean (converts to a 0 or 1 - not a python bool type) 
def tobool(args=[]):
    stack.append(int(bool(stack.pop())))
    
"""
Reads all the the lines of code from the input files.

Separates the instruction from the argument on each line, 
dispatches each instruction to the appropriate function w/ its arguments
"""
def run(inputfile):
    code = inputfile.readlines() # Reads all the code lines from the file
    global pc
    pc = 0
    while pc < len(code):
        line = code[pc].rstrip() # Strip endline from code
        if line: # non-empty line
            instruction = line.split()[0].lower()
            argument = [" ".join(line.split()[1:])]
            pc += 1 # Point program-counter to next instruction
            # Invoke the instruction with the named-function and pass it the argument (or empty list)
            try:
                if verbose:
                    print "Processing instruction: %s"  % line
                globals()[instruction](args=argument)
                if verbose:
                    from pprint import pprint
                    pprint(stack)
                    pprint(memory)
                    print "SP: ",sp
                    print ""
            except Exception,e:
                print "Exception on line %d: '%s'\n\t%s" % (pc,line,e)
                if verbose:
                    from traceback import print_exc
                    print_exc(e)
                sys.exit(1)
        else:
            pc += 1
                
def main():
    # Processor command line arguments
    if len(sys.argv) != 2:
        print "Usage: python vm.py <input file>"
        print "\tUse '-' if <input file> is standard-in"
        sys.exit(1)
    else:
        if sys.argv[1] == "-":
            inputfile = sys.stdin
        else:
            try:
                inputfile = open(sys.argv[1],'r')
            except Exception,e:
                print e
                sys.exit(1)
    
    run(inputfile)
    
if __name__ == '__main__':
    main()
